home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 2 / AACD 2.iso / AACD / Magazine / GraphicsCards / StormMesa / src-glu / polytest.c < prev    next >
C/C++ Source or Header  |  1998-12-15  |  27KB  |  1,044 lines
  1. /* $Id: polytest.c,v 1.6 1998/07/26 02:08:52 brianp Exp $ */
  2.  
  3. /*
  4.  * Mesa 3-D graphics library
  5.  * Version:  2.4
  6.  * Copyright (C) 1995-1997  Brian Paul
  7.  *
  8.  * This library is free software; you can redistribute it and/or
  9.  * modify it under the terms of the GNU Library General Public
  10.  * License as published by the Free Software Foundation; either
  11.  * version 2 of the License, or (at your option) any later version.
  12.  *
  13.  * This library is distributed in the hope that it will be useful,
  14.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16.  * Library General Public License for more details.
  17.  *
  18.  * You should have received a copy of the GNU Library General Public
  19.  * License along with this library; if not, write to the Free
  20.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  21.  */
  22.  
  23.  
  24. /*
  25.  * $Log: polytest.c,v $
  26.  * Revision 1.6  1998/07/26 02:08:52  brianp
  27.  * updated for Windows compilation per Ted Jump
  28.  *
  29.  * Revision 1.5  1997/10/29 02:02:20  brianp
  30.  * various MS Windows compiler changes (David Bucciarelli, v20 3dfx driver)
  31.  *
  32.  * Revision 1.4  1997/07/24 01:28:44  brianp
  33.  * changed precompiled header symbol from PCH to PC_HEADER
  34.  *
  35.  * Revision 1.3  1997/05/28 02:29:38  brianp
  36.  * added support for precompiled headers (PCH), inserted APIENTRY keyword
  37.  *
  38.  * Revision 1.2  1997/05/08 01:53:21  brianp
  39.  * fixed memory leak in free_current_polygon() reported by Randy Frank
  40.  *
  41.  * Revision 1.1  1996/09/27 01:19:39  brianp
  42.  * Initial revision
  43.  *
  44.  */
  45.  
  46.  
  47. /*
  48.  * This file is part of the polygon tesselation code contributed by
  49.  * Bogdan Sikorski
  50.  */
  51.  
  52.  
  53. #ifdef PC_HEADER
  54. #include "all.h"
  55. #else
  56. #include <math.h>
  57. #include <stdlib.h>
  58. #include "gluP.h"
  59. #include "tess.h"
  60. #endif
  61.  
  62.  
  63.  
  64. static GLenum store_polygon_as_contour(GLUtriangulatorObj *);
  65. static void free_current_polygon(tess_polygon *);
  66. static void prepare_projection_info(GLUtriangulatorObj *);
  67. static GLdouble twice_the_polygon_area(tess_vertex *,tess_vertex *);
  68. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *);
  69. void tess_find_contour_hierarchies(GLUtriangulatorObj *);
  70. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *);
  71. static GLenum contours_overlap(tess_contour *, tess_polygon *);
  72. static GLenum is_contour_contained_in(tess_contour *,tess_contour *);
  73. static void add_new_exterior(GLUtriangulatorObj *,tess_contour *);
  74. static void add_new_interior(GLUtriangulatorObj *,tess_contour *,
  75.     tess_contour *);
  76. static void add_interior_with_hierarchy_check(GLUtriangulatorObj *,
  77.     tess_contour *,tess_contour *);
  78. static void reverse_hierarchy_and_add_exterior(GLUtriangulatorObj *,
  79.     tess_contour *,tess_contour *);
  80. static GLboolean point_in_polygon(tess_contour *,GLdouble,GLdouble);
  81. static void shift_interior_to_exterior(GLUtriangulatorObj *,tess_contour *);
  82. static void add_exterior_with_check(GLUtriangulatorObj *,tess_contour *,
  83.     tess_contour *);
  84. static GLenum cut_out_hole(GLUtriangulatorObj *,tess_contour *,
  85.     tess_contour *);
  86. static GLenum merge_hole_with_contour(GLUtriangulatorObj *,
  87.     tess_contour *,tess_contour *,tess_vertex *,
  88.     tess_vertex *);
  89.  
  90. static GLenum
  91. find_normal(GLUtriangulatorObj *tobj)
  92. {
  93.     tess_polygon *polygon=tobj->current_polygon;
  94.     tess_vertex *va,*vb,*vc;
  95.     GLdouble A,B,C;
  96.     GLdouble A0,A1,A2,B0,B1,B2;
  97.  
  98.     va=polygon->vertices;
  99.     vb=va->next;
  100.     A0=vb->location[0]-va->location[0];
  101.     A1=vb->location[1]-va->location[1];
  102.     A2=vb->location[2]-va->location[2];
  103.     for(vc=vb->next;vc!=va;vc=vc->next)
  104.     {
  105.         B0=vc->location[0]-va->location[0];
  106.         B1=vc->location[1]-va->location[1];
  107.         B2=vc->location[2]-va->location[2];
  108.         A=A1*B2-A2*B1;
  109.         B=A2*B0-A0*B2;
  110.         C=A0*B1-A1*B0;
  111.         if(fabs(A)>EPSILON || fabs(B)>EPSILON || fabs(C)>EPSILON)
  112.         {
  113.             polygon->A=A;
  114.             polygon->B=B;
  115.             polygon->C=C;
  116.             polygon->D= -A*va->location[0]-B*va->location[1]-C*va->location[2];
  117.             return GLU_NO_ERROR;
  118.         }
  119.     }
  120.     tess_call_user_error(tobj,GLU_TESS_ERROR7);
  121.     return GLU_ERROR;
  122. }
  123.  
  124. void
  125. tess_test_polygon( GLUtriangulatorObj *tobj )
  126. {
  127.     tess_polygon *polygon=tobj->current_polygon;
  128.  
  129.     /* any vertices defined? */
  130.     if(polygon->vertex_cnt<3)
  131.     {
  132.         free_current_polygon(polygon);
  133.         return;
  134.     }
  135.     /* wrap pointers */
  136.     polygon->last_vertex->next=polygon->vertices;
  137.     polygon->vertices->previous=polygon->last_vertex;
  138.     /* determine the normal */
  139.     if(find_normal(tobj)==GLU_ERROR)
  140.         return;
  141.     /* compare the normals of previously defined contours and this one */
  142.     /* first contour define ? */
  143.     if(tobj->contours==NULL)
  144.     {
  145.         tobj->A=polygon->A;
  146.         tobj->B=polygon->B;
  147.         tobj->C=polygon->C;
  148.         tobj->D=polygon->D;
  149.         /* determine the best projection to use */
  150.         if(fabs(polygon->A) > fabs(polygon->B))
  151.             if(fabs(polygon->A) > fabs(polygon->C))
  152.                 tobj->projection=OYZ;
  153.             else
  154.                 tobj->projection=OXY;
  155.         else
  156.             if(fabs(polygon->B) > fabs(polygon->C))
  157.                 tobj->projection=OXZ;
  158.             else
  159.                 tobj->projection=OXY;
  160.     }
  161.     else
  162.     {
  163.         GLdouble a[3],b[3];
  164.         tess_vertex *vertex=polygon->vertices;
  165.  
  166.         a[0]=tobj->A;
  167.         a[1]=tobj->B;
  168.         a[2]=tobj->C;
  169.         b[0]=polygon->A;
  170.         b[1]=polygon->B;
  171.         b[2]=polygon->C;
  172.  
  173.         /* compare the normals */
  174.         if( fabs(a[1]*b[2]-a[2]*b[1]) > EPSILON ||
  175.             fabs(a[2]*b[0]-a[0]*b[2]) > EPSILON ||
  176.             fabs(a[0]*b[1]-a[1]*b[0]) > EPSILON)
  177.         {
  178.             /* not coplanar */
  179.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  180.             return;
  181.         }
  182.         /* the normals are parallel - test for plane equation */
  183.         if(fabs(a[0]*vertex->location[0]+a[1]*vertex->location[1]+
  184.             a[2]*vertex->location[2]+tobj->D) > EPSILON)
  185.         {
  186.             /* not the same plane */
  187.             tess_call_user_error(tobj,GLU_TESS_ERROR9);
  188.             return;
  189.         }
  190.     }
  191.     prepare_projection_info(tobj);
  192.     if(verify_edge_vertex_intersections(tobj)==GLU_ERROR)
  193.         return;
  194.     if(test_for_overlapping_contours(tobj)==GLU_ERROR)
  195.         return;
  196.     if(store_polygon_as_contour(tobj)==GLU_ERROR)
  197.         return;
  198. }
  199.  
  200. static GLenum test_for_overlapping_contours(GLUtriangulatorObj *tobj)
  201. {
  202.     tess_contour *contour;
  203.     tess_polygon *polygon;
  204.  
  205.     polygon=tobj->current_polygon;
  206.     for(contour=tobj->contours;contour!=NULL;contour=contour->next)
  207.         if(contours_overlap(contour,polygon)!=GLU_NO_ERROR)
  208.         {
  209.             tess_call_user_error(tobj,GLU_TESS_ERROR5);
  210.             return GLU_ERROR;
  211.         }
  212.     return GLU_NO_ERROR;
  213. }
  214.  
  215. static GLenum store_polygon_as_contour(GLUtriangulatorObj *tobj)
  216. {
  217.     tess_polygon *polygon=tobj->current_polygon;
  218.     tess_contour *contour=tobj->contours;
  219.  
  220.     /* the first contour defined */
  221.     if(contour==NULL)
  222.     {
  223.         if((contour=(tess_contour *)malloc(
  224.             sizeof(tess_contour)))==NULL)
  225.         {
  226.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  227.             free_current_polygon(polygon);
  228.             return GLU_ERROR;
  229.         }
  230.         tobj->contours=tobj->last_contour=contour;
  231.         contour->next=contour->previous=NULL;
  232.     }
  233.     else
  234.     {
  235.         if((contour=(tess_contour *)malloc(
  236.             sizeof(tess_contour)))==NULL)
  237.         {
  238.             tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  239.             free_current_polygon(polygon);
  240.             return GLU_ERROR;
  241.         }
  242.         contour->previous=tobj->last_contour;
  243.         tobj->last_contour->next=contour;
  244.         tobj->last_contour=contour;
  245.         contour->next=NULL;
  246.     }
  247.     /* mark all vertices in new contour as not special */
  248.     /* and all are boundary edges */
  249.     {
  250.         tess_vertex *vertex;
  251.         GLuint vertex_cnt,i;
  252.  
  253.         for(vertex=polygon->vertices , i=0 , vertex_cnt=polygon->vertex_cnt;
  254.             i<vertex_cnt;
  255.             vertex=vertex->next , i++)
  256.         {
  257.             vertex->shadow_vertex=NULL;
  258.             vertex->edge_flag=GL_TRUE;
  259.         }
  260.     }
  261.     contour->vertex_cnt=polygon->vertex_cnt;
  262.     contour->area=polygon->area;
  263.     contour->orientation=polygon->orientation;
  264.     contour->type=GLU_UNKNOWN;
  265.     contour->vertices=polygon->vertices;
  266.     contour->last_vertex=polygon->last_vertex;
  267.     polygon->vertices=polygon->last_vertex=NULL;
  268.     polygon->vertex_cnt=0;
  269.     ++(tobj->contour_cnt);
  270.     return GLU_NO_ERROR;
  271. }
  272.  
  273. static void free_current_polygon(tess_polygon *polygon)
  274. {
  275.     tess_vertex *vertex,*vertex_tmp;
  276.     GLuint    i;
  277.  
  278.     /* free current_polygon structures */
  279.     for(vertex=polygon->vertices,i=0;i<polygon->vertex_cnt;i++)
  280.     {
  281.         vertex_tmp=vertex->next;
  282.         free(vertex);
  283.         vertex=vertex_tmp;
  284.     }
  285.     polygon->vertices=polygon->last_vertex=NULL;
  286.     polygon->vertex_cnt=0;
  287. }
  288.  
  289. static void prepare_projection_info(GLUtriangulatorObj *tobj)
  290. {
  291.     tess_polygon *polygon=tobj->current_polygon;
  292.     tess_vertex *vertex,*last_vertex_ptr;
  293.     GLdouble area;
  294.  
  295.     last_vertex_ptr=polygon->last_vertex;
  296.     switch(tobj->projection)
  297.     {
  298.         case OXY:
  299.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  300.                 vertex=vertex->next)
  301.             {
  302.                 vertex->x=vertex->location[0];
  303.                 vertex->y=vertex->location[1];
  304.             }
  305.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  306.             last_vertex_ptr->y=last_vertex_ptr->location[1];
  307.             break;
  308.         case OXZ:
  309.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  310.                 vertex=vertex->next)
  311.             {
  312.                 vertex->x=vertex->location[0];
  313.                 vertex->y=vertex->location[2];
  314.             }
  315.             last_vertex_ptr->x=last_vertex_ptr->location[0];
  316.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  317.             break;
  318.         case OYZ:
  319.             for(vertex=polygon->vertices;vertex!=last_vertex_ptr;
  320.                 vertex=vertex->next)
  321.             {
  322.                 vertex->x=vertex->location[1];
  323.                 vertex->y=vertex->location[2];
  324.             }
  325.             last_vertex_ptr->x=last_vertex_ptr->location[1];
  326.             last_vertex_ptr->y=last_vertex_ptr->location[2];
  327.             break;
  328.     }
  329.     area=twice_the_polygon_area(polygon->vertices,polygon->last_vertex);
  330.     if(area >= 0.0)
  331.     {
  332.         polygon->orientation=GLU_CCW;
  333.         polygon->area=area;
  334.     }
  335.     else
  336.     {
  337.         polygon->orientation=GLU_CW;
  338.         polygon->area= -area;
  339.     }
  340. }
  341.  
  342. static GLdouble twice_the_polygon_area(tess_vertex *vertex,
  343.     tess_vertex *last_vertex)
  344. {
  345.     tess_vertex *next;
  346.     GLdouble area,x,y;
  347.  
  348.     area=0.0;
  349.     x=vertex->x;
  350.     y=vertex->y;
  351.     vertex=vertex->next;
  352.     for(; vertex!=last_vertex; vertex=vertex->next)
  353.     {
  354.         next=vertex->next;
  355.         area+=(vertex->x - x)*(next->y - y) - (vertex->y - y)*(next->x - x);
  356.     }
  357.     return area;
  358. }
  359.  
  360. /* test if edges ab and cd intersect */
  361. /* if not return GLU_NO_ERROR, else if cross return GLU_TESS_ERROR8, */
  362. /* else if adjacent return GLU_TESS_ERROR4 */
  363. static GLenum edge_edge_intersect(
  364.     tess_vertex *a,
  365.     tess_vertex *b,
  366.     tess_vertex *c,
  367.     tess_vertex *d)
  368. {
  369.     GLdouble denom,r,s;
  370.     GLdouble xba,ydc,yba,xdc,yac,xac;
  371.  
  372.     xba=b->x - a->x;
  373.     yba=b->y - a->y;
  374.     xdc=d->x - c->x;
  375.     ydc=d->y - c->y;
  376.     xac=a->x - c->x;
  377.     yac=a->y - c->y;
  378.     denom= xba*ydc - yba*xdc;
  379.     r = yac*xdc - xac*ydc;
  380.     /* parallel? */
  381.     if(fabs(denom) < EPSILON)
  382.     {
  383.         if(fabs(r) < EPSILON)
  384.         {
  385.             /* colinear */
  386.             if(fabs(xba) < EPSILON)
  387.             {
  388.                 /* compare the Y coordinate */
  389.                 if(yba > 0.0)
  390.                 {
  391.                     if((fabs(a->y - c->y)<EPSILON && fabs(c->y - b->y)<EPSILON)
  392.                         ||
  393.                         (fabs(a->y - d->y)<EPSILON && fabs(d->y - b->y)<EPSILON))
  394.                     return GLU_TESS_ERROR4;
  395.  
  396.                 }
  397.                 else
  398.                 {
  399.                     if((fabs(b->y - c->y)<EPSILON && fabs(c->y - a->y)<EPSILON)
  400.                         ||
  401.                         (fabs(b->y - d->y)<EPSILON && fabs(d->y - a->y)<EPSILON))
  402.                     return GLU_TESS_ERROR4;
  403.                 }
  404.             }
  405.             else
  406.             {
  407.                 /* compare the X coordinate */
  408.                 if(xba > 0.0)
  409.                 {
  410.                     if((fabs(a->x - c->x)<EPSILON && fabs(c->x - b->x)<EPSILON)
  411.                         ||
  412.                         (fabs(a->x - d->x)<EPSILON && fabs(d->x - b->x)<EPSILON))
  413.                     return GLU_TESS_ERROR4;
  414.                 }
  415.                 else
  416.                 {
  417.                     if((fabs(b->x - c->x)<EPSILON && fabs(c->x - a->x)<EPSILON)
  418.                         ||
  419.                         (fabs(b->x - d->x)<EPSILON && fabs(d->x - a->x)<EPSILON))
  420.                     return GLU_TESS_ERROR4;
  421.                 }
  422.             }
  423.         }
  424.         return GLU_NO_ERROR;
  425.     }
  426.     r /= denom;
  427.     s = (yac*xba - xac*yba) / denom;
  428.     /* test if one vertex lies on other edge */
  429.     if(((fabs(r) < EPSILON || (r < 1.0+EPSILON && r > 1.0-EPSILON)) &&
  430.         s > -EPSILON && s < 1.0+EPSILON) ||
  431.         ((fabs(s) < EPSILON || (s < 1.0+EPSILON && s > 1.0-EPSILON)) &&
  432.         r > -EPSILON && r < 1.0+EPSILON))
  433.     {
  434.         return GLU_TESS_ERROR4;
  435.     }
  436.     /* test for crossing */
  437.     if(r > -EPSILON && r < 1.0+EPSILON &&
  438.         s > -EPSILON && s < 1.0+EPSILON)
  439.     {
  440.         return GLU_TESS_ERROR8;
  441.     }
  442.     return GLU_NO_ERROR;
  443. }
  444.  
  445. static GLenum verify_edge_vertex_intersections(GLUtriangulatorObj *tobj)
  446. {
  447.     tess_polygon *polygon=tobj->current_polygon;
  448.     tess_vertex *vertex1,*last_vertex,*vertex2;
  449.     GLenum test;
  450.  
  451.     last_vertex=polygon->last_vertex;
  452.     vertex1=last_vertex;
  453.     for(vertex2=vertex1->next->next;
  454.         vertex2->next!=last_vertex;
  455.         vertex2=vertex2->next)
  456.     {
  457.         test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  458.             vertex2->next);
  459.         if(test!=GLU_NO_ERROR)
  460.         {
  461.             tess_call_user_error(tobj,test);
  462.             return GLU_ERROR;
  463.         }
  464.     }
  465.     for(vertex1=polygon->vertices;
  466.         vertex1->next->next!=last_vertex;
  467.         vertex1=vertex1->next)
  468.     {
  469.         for(vertex2=vertex1->next->next;
  470.             vertex2!=last_vertex;
  471.             vertex2=vertex2->next)
  472.         {
  473.             test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  474.                 vertex2->next);
  475.             if(test!=GLU_NO_ERROR)
  476.             {
  477.                 tess_call_user_error(tobj,test);
  478.                 return GLU_ERROR;
  479.             }
  480.         }
  481.     }
  482.     return GLU_NO_ERROR;
  483. }
  484.  
  485. static int
  486. #ifdef WIN32
  487. __cdecl
  488. #endif
  489. area_compare(const void *a,const void *b)
  490. {
  491.     GLdouble area1,area2;
  492.  
  493.     area1=(*((tess_contour **)a))->area;
  494.     area2=(*((tess_contour **)b))->area;
  495.     if(area1 < area2)
  496.         return 1;
  497.     if(area1 > area2)
  498.         return -1;
  499.     return 0;
  500. }
  501.  
  502. void tess_find_contour_hierarchies(GLUtriangulatorObj *tobj)
  503. {
  504.     tess_contour **contours; /* dinamic array of pointers */
  505.     tess_contour *tmp_contour_ptr=tobj->contours;
  506.     GLuint cnt,i;
  507.     GLenum result;
  508.     GLboolean hierarchy_changed;
  509.  
  510.     /* any contours? */
  511.     if(tobj->contour_cnt < 2)
  512.     {
  513.         tobj->contours->type=GLU_EXTERIOR;
  514.         return;
  515.     }
  516.     if((contours=(tess_contour **)
  517.         malloc(sizeof(tess_contour *)*(tobj->contour_cnt)))==NULL)
  518.     {
  519.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  520.         return;
  521.     }
  522.     for(tmp_contour_ptr=tobj->contours , cnt=0;
  523.         tmp_contour_ptr!=NULL;
  524.         tmp_contour_ptr=tmp_contour_ptr->next)
  525.         contours[cnt++]=tmp_contour_ptr;
  526.     /* now sort the contours in decreasing area size order */
  527.     qsort((void *)contours,(size_t)cnt,(size_t)sizeof(tess_contour *),area_compare);
  528.     /* we leave just the first contour - remove others from list */
  529.     tobj->contours=contours[0];
  530.     tobj->contours->next=tobj->contours->previous=NULL;
  531.     tobj->last_contour=tobj->contours;
  532.     tobj->contour_cnt=1;
  533.     /* first contour is the one with greatest area */
  534.     /* must be EXTERIOR */
  535.     tobj->contours->type=GLU_EXTERIOR;
  536.     tmp_contour_ptr=tobj->contours;
  537.     /* now we play! */
  538.     for(i=1;i<cnt;i++)
  539.     {
  540.         hierarchy_changed=GL_FALSE;
  541.         for(tmp_contour_ptr=tobj->contours;
  542.             tmp_contour_ptr!=NULL;
  543.             tmp_contour_ptr=tmp_contour_ptr->next)
  544.         {
  545.             if(tmp_contour_ptr->type==GLU_EXTERIOR)
  546.             {
  547.                 /* check if contour completely contained in EXTERIOR */
  548.                 result=is_contour_contained_in(tmp_contour_ptr,contours[i]);
  549.                 switch(result)
  550.                 {
  551.                     case GLU_INTERIOR:
  552.                         /* now we have to check if contour is inside interiors */
  553.                         /* or not */
  554.                         /* any interiors? */
  555.                         if(tmp_contour_ptr->next!=NULL &&
  556.                             tmp_contour_ptr->next->type==GLU_INTERIOR)
  557.                         {
  558.                             /* for all interior, check if inside any of them */
  559.                             /* if not inside any of interiors, its another */
  560.                             /* interior */
  561.                             /* or it may contain some interiors, then change */
  562.                             /* the contained interiors to exterior ones */
  563.                             add_interior_with_hierarchy_check(tobj,
  564.                                 tmp_contour_ptr,contours[i]);
  565.                         }
  566.                         else
  567.                         {
  568.                             /* not in interior, add as new interior contour */
  569.                             add_new_interior(tobj,tmp_contour_ptr,contours[i]);
  570.                         }
  571.                         hierarchy_changed=GL_TRUE;
  572.                         break;
  573.                     case GLU_EXTERIOR:
  574.                         /* ooops, the marked as EXTERIOR (contours[i]) is */
  575.                         /* actually an interior of tmp_contour_ptr */
  576.                         /*  reverse the local hierarchy */
  577.                         reverse_hierarchy_and_add_exterior(tobj,tmp_contour_ptr,
  578.                             contours[i]);
  579.                         hierarchy_changed=GL_TRUE;
  580.                         break;
  581.                     case GLU_NO_ERROR:
  582.                         break;
  583.                     default:
  584.                         abort();
  585.                 }
  586.             }
  587.             if(hierarchy_changed)
  588.                 break; /* break from for loop */
  589.         }
  590.         if(hierarchy_changed==GL_FALSE)
  591.         {
  592.             /* disjoint with all contours, add to contour list */
  593.             add_new_exterior(tobj,contours[i]);
  594.         }
  595.     }
  596.     free(contours);
  597. }
  598.  
  599. /* returns GLU_INTERIOR if inner is completey enclosed within outer */
  600. /* returns GLU_EXTERIOR if outer is completely enclosed within inner */
  601. /* returns GLU_NO_ERROR if contours are disjoint */
  602. static GLenum is_contour_contained_in(
  603.     tess_contour *outer,
  604.     tess_contour *inner)
  605. {
  606.     GLenum relation_flag;
  607.  
  608.     /* set relation_flag to relation of containment of first inner vertex */
  609.     /* regarding outer contour */
  610.     if(point_in_polygon(outer,inner->vertices->x,inner->vertices->y))
  611.         relation_flag=GLU_INTERIOR;
  612.     else
  613.         relation_flag=GLU_EXTERIOR;
  614.     if(relation_flag==GLU_INTERIOR)
  615.         return GLU_INTERIOR;
  616.     if(point_in_polygon(inner,outer->vertices->x,outer->vertices->y))
  617.         return GLU_EXTERIOR;
  618.     return GLU_NO_ERROR;
  619. }
  620.  
  621. static GLboolean point_in_polygon(
  622.     tess_contour *contour,
  623.     GLdouble x,
  624.     GLdouble y)
  625. {
  626.     tess_vertex *v1,*v2;
  627.     GLuint i,vertex_cnt;
  628.     GLdouble xp1,yp1,xp2,yp2;
  629.     GLboolean tst;
  630.  
  631.     tst=GL_FALSE;
  632.     v1=contour->vertices;
  633.     v2=contour->vertices->previous;
  634.     for(i=0 , vertex_cnt=contour->vertex_cnt;
  635.         i < vertex_cnt;
  636.         i++)
  637.     {
  638.         xp1=v1->x;
  639.         yp1=v1->y;
  640.         xp2=v2->x;
  641.         yp2=v2->y;
  642.         if ((((yp1<=y) && (y<yp2)) || ((yp2<=y)  && (y<yp1))) &&
  643.             (x < (xp2 - xp1) * (y - yp1) /  (yp2 - yp1) + xp1))
  644.                 tst = (tst==GL_FALSE ? GL_TRUE : GL_FALSE);
  645.         v2=v1;
  646.         v1=v1->next;
  647.     }
  648.     return tst;
  649. }
  650.  
  651. static GLenum contours_overlap(
  652.     tess_contour *contour,
  653.     tess_polygon *polygon)
  654. {
  655.     tess_vertex *vertex1,*vertex2;
  656.     GLuint vertex1_cnt,vertex2_cnt,i,j;
  657.     GLenum test;
  658.  
  659.     vertex1=contour->vertices;
  660.     vertex2=polygon->vertices;
  661.     vertex1_cnt=contour->vertex_cnt;
  662.     vertex2_cnt=polygon->vertex_cnt;
  663.     for(i=0; i<vertex1_cnt; vertex1=vertex1->next , i++)
  664.     {
  665.         for(j=0; j<vertex2_cnt; vertex2=vertex2->next , j++)
  666.             if((test=edge_edge_intersect(vertex1,vertex1->next,vertex2,
  667.                 vertex2->next))!=GLU_NO_ERROR)
  668.                 return test;
  669.     }
  670.     return GLU_NO_ERROR;
  671. }
  672.  
  673. static void add_new_exterior(
  674.     GLUtriangulatorObj *tobj,
  675.     tess_contour *contour)
  676. {
  677.     contour->type=GLU_EXTERIOR;
  678.     contour->next=NULL;
  679.     contour->previous=tobj->last_contour;
  680.     tobj->last_contour->next=contour;
  681.     tobj->last_contour=contour;
  682. }
  683.  
  684. static void add_new_interior(
  685.     GLUtriangulatorObj *tobj,
  686.     tess_contour *outer,
  687.     tess_contour *contour)
  688. {
  689.     contour->type=GLU_INTERIOR;
  690.     contour->next=outer->next;
  691.     contour->previous=outer;
  692.     if(outer->next!=NULL)
  693.         outer->next->previous=contour;
  694.     outer->next=contour;
  695.     if(tobj->last_contour==outer)
  696.         tobj->last_contour=contour;
  697. }
  698.  
  699. static void add_interior_with_hierarchy_check(
  700.     GLUtriangulatorObj *tobj,
  701.     tess_contour *outer,
  702.     tess_contour *contour)
  703. {
  704.     tess_contour *ptr;
  705.  
  706.     /* for all interiors of outer check if they are interior of contour */
  707.     /* if so, change that interior to exterior and move it of of the */
  708.     /* interior sequence */
  709.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  710.     {
  711.         GLenum test;
  712.  
  713.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  714.         {
  715.             test=is_contour_contained_in(ptr,contour);
  716.             switch(test)
  717.             {
  718.                 case GLU_INTERIOR:
  719.                     /* contour is contained in one of the interiors */
  720.                     /* check if possibly contained in other exteriors */
  721.                     /* move ptr to first EXTERIOR */
  722.                     for(;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next);
  723.                     if(ptr==NULL)
  724.                         /* another exterior */
  725.                         add_new_exterior(tobj,contour);
  726.                     else
  727.                         add_exterior_with_check(tobj,ptr,contour);
  728.                     return;
  729.                 case GLU_EXTERIOR:
  730.                     /* one of the interiors is contained in the contour */
  731.                     /* change it to EXTERIOR, and shift it away from the */
  732.                     /* interior sequence */
  733.                     shift_interior_to_exterior(tobj,ptr);
  734.                     break;
  735.                 case GLU_NO_ERROR:
  736.                     /* disjoint */
  737.                     break;
  738.                 default:
  739.                     abort();
  740.             }
  741.         }
  742.     }
  743.     /* add contour to the interior sequence */
  744.     add_new_interior(tobj,outer,contour);
  745. }
  746.  
  747. static void reverse_hierarchy_and_add_exterior(
  748.     GLUtriangulatorObj *tobj,
  749.     tess_contour *outer,
  750.     tess_contour *contour)
  751. {
  752.     tess_contour *ptr;
  753.  
  754.     /* reverse INTERIORS to EXTERIORS */
  755.     /* any INTERIORS? */
  756.     if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  757.         for(ptr=outer->next;ptr!=NULL && ptr->type==GLU_INTERIOR;ptr=ptr->next)
  758.             ptr->type=GLU_EXTERIOR;
  759.     /* the outer now becomes inner */
  760.     outer->type=GLU_INTERIOR;
  761.     /* contour is the EXTERIOR */
  762.     contour->next=outer;
  763.     if(tobj->contours==outer)
  764.     {
  765.         /* first contour beeing reversed */
  766.         contour->previous=NULL;
  767.         tobj->contours=contour;
  768.     }
  769.     else
  770.     {
  771.         outer->previous->next=contour;
  772.         contour->previous=outer->previous;
  773.     }
  774.     outer->previous=contour;
  775. }
  776.  
  777. static void shift_interior_to_exterior(
  778.     GLUtriangulatorObj *tobj,
  779.     tess_contour *contour)
  780. {
  781.     contour->previous->next=contour->next;
  782.     if(contour->next!=NULL)
  783.         contour->next->previous=contour->previous;
  784.     else
  785.         tobj->last_contour=contour->previous;
  786. }
  787.  
  788. static void add_exterior_with_check(
  789.     GLUtriangulatorObj *tobj,
  790.     tess_contour *outer,
  791.     tess_contour *contour)
  792. {
  793.     GLenum test;
  794.  
  795.     /* this contour might be interior to further exteriors - check */
  796.     /* if not, just add as a new exterior */
  797.     for(;outer!=NULL && outer->type==GLU_EXTERIOR;outer=outer->next)
  798.     {
  799.         test=is_contour_contained_in(outer,contour);
  800.         switch(test)
  801.         {
  802.             case GLU_INTERIOR:
  803.                 /* now we have to check if contour is inside interiors */
  804.                 /* or not */
  805.                 /* any interiors? */
  806.                 if(outer->next!=NULL && outer->next->type==GLU_INTERIOR)
  807.                 {
  808.                     /* for all interior, check if inside any of them */
  809.                     /* if not inside any of interiors, its another */
  810.                     /* interior */
  811.                     /* or it may contain some interiors, then change */
  812.                     /* the contained interiors to exterior ones */
  813.                     add_interior_with_hierarchy_check(tobj,
  814.                         outer,contour);
  815.                 }
  816.                 else
  817.                 {
  818.                     /* not in interior, add as new interior contour */
  819.                     add_new_interior(tobj,outer,contour);
  820.                 }
  821.                 return;
  822.             case GLU_NO_ERROR:
  823.                 /* disjoint */
  824.                 break;
  825.             default:
  826.                 abort();
  827.         }
  828.     }
  829.     /* add contour to the exterior sequence */
  830.     add_new_exterior(tobj,contour);
  831. }
  832.  
  833. void tess_handle_holes(GLUtriangulatorObj *tobj)
  834. {
  835.     tess_contour *contour,*hole;
  836.     GLenum exterior_orientation;
  837.  
  838.     /* verify hole orientation */
  839.     for(contour=tobj->contours;contour!=NULL;)
  840.     {
  841.         exterior_orientation=contour->orientation;
  842.         for(contour=contour->next;
  843.             contour!=NULL && contour->type==GLU_INTERIOR;
  844.             contour=contour->next)
  845.         {
  846.             if(contour->orientation==exterior_orientation)
  847.             {
  848.                 tess_call_user_error(tobj,GLU_TESS_ERROR5);
  849.                 return;
  850.             }
  851.         }
  852.     }
  853.     /* now cut-out holes */
  854.     for(contour=tobj->contours;contour!=NULL;)
  855.     {
  856.         hole=contour->next;
  857.         while(hole!=NULL && hole->type==GLU_INTERIOR)
  858.         {
  859.             if(cut_out_hole(tobj,contour,hole)==GLU_ERROR)
  860.                 return;
  861.             hole=contour->next;
  862.         }
  863.         contour=contour->next;
  864.     }
  865. }
  866.  
  867. static GLenum cut_out_hole(
  868.     GLUtriangulatorObj *tobj,
  869.     tess_contour *contour,
  870.     tess_contour *hole)
  871. {
  872.     tess_contour *tmp_hole;
  873.     tess_vertex *v1,*v2,*tmp_vertex;
  874.     GLuint vertex1_cnt,vertex2_cnt,tmp_vertex_cnt;
  875.     GLuint i,j,k;
  876.     GLenum test;
  877.  
  878.     /* find an edge connecting contour and hole not intersecting any other */
  879.     /* edge belonging to either the contour or any of the other holes */
  880.     for(v1=contour->vertices , vertex1_cnt=contour->vertex_cnt , i=0;
  881.         i<vertex1_cnt;
  882.         i++ , v1=v1->next)
  883.     {
  884.         for(v2=hole->vertices , vertex2_cnt=hole->vertex_cnt , j=0;
  885.             j<vertex2_cnt;
  886.             j++ , v2=v2->next)
  887.         {
  888.             /* does edge (v1,v2) intersect any edge of contour */
  889.             for(tmp_vertex=contour->vertices , tmp_vertex_cnt=contour->vertex_cnt ,
  890.                     k=0;
  891.                 k<tmp_vertex_cnt;
  892.                 tmp_vertex=tmp_vertex->next , k++)
  893.             {
  894.                 /* skip edge tests for edges directly connected */
  895.                 if(v1==tmp_vertex || v1==tmp_vertex->next)
  896.                     continue;
  897.                 test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  898.                 if(test!=GLU_NO_ERROR)
  899.                     break;
  900.             }
  901.             if(test==GLU_NO_ERROR)
  902.             {
  903.                 /* does edge (v1,v2) intersect any edge of hole */
  904.                 for(tmp_vertex=hole->vertices ,
  905.                         tmp_vertex_cnt=hole->vertex_cnt , k=0;
  906.                     k<tmp_vertex_cnt;
  907.                     tmp_vertex=tmp_vertex->next , k++)
  908.                 {
  909.                     /* skip edge tests for edges directly connected */
  910.                     if(v2==tmp_vertex || v2==tmp_vertex->next)
  911.                         continue;
  912.                     test=edge_edge_intersect(v1,v2,tmp_vertex,tmp_vertex->next);
  913.                     if(test!=GLU_NO_ERROR)
  914.                         break;
  915.                 }
  916.                 if(test==GLU_NO_ERROR)
  917.                 {
  918.                     /* does edge (v1,v2) intersect any other hole? */
  919.                     for(tmp_hole=hole->next;
  920.                         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  921.                         tmp_hole=tmp_hole->next)
  922.                     {
  923.                         /* does edge (v1,v2) intersect any edge of hole */
  924.                         for(tmp_vertex=tmp_hole->vertices ,
  925.                                 tmp_vertex_cnt=tmp_hole->vertex_cnt , k=0;
  926.                             k<tmp_vertex_cnt;
  927.                             tmp_vertex=tmp_vertex->next , k++)
  928.                         {
  929.                             test=edge_edge_intersect(v1,v2,tmp_vertex,
  930.                                 tmp_vertex->next);
  931.                             if(test!=GLU_NO_ERROR)
  932.                                 break;
  933.                         }
  934.                         if(test!=GLU_NO_ERROR)
  935.                             break;
  936.                     }
  937.                 }
  938.             }
  939.             if(test==GLU_NO_ERROR)
  940.             {
  941.                 /* edge (v1,v2) is good for eliminating the hole */
  942.                 if(merge_hole_with_contour(tobj,contour,hole,v1,v2)
  943.                     ==GLU_NO_ERROR)
  944.                     return GLU_NO_ERROR;
  945.                 else
  946.                     return GLU_ERROR;
  947.             }
  948.         }
  949.     }
  950.     /* other holes are blocking all possible connections of hole */
  951.     /* with contour, we shift this hole as the last hole and retry */
  952.     for(tmp_hole=hole;
  953.         tmp_hole!=NULL && tmp_hole->type==GLU_INTERIOR;
  954.         tmp_hole=tmp_hole->next);
  955.     contour->next=hole->next;
  956.     hole->next->previous=contour;
  957.     if(tmp_hole==NULL)
  958.     {
  959.         /* last EXTERIOR contour, shift hole as last contour */
  960.         hole->next=NULL;
  961.         hole->previous=tobj->last_contour;
  962.         tobj->last_contour->next=hole;
  963.         tobj->last_contour=hole;
  964.     }
  965.     else
  966.     {
  967.         tmp_hole->previous->next=hole;
  968.         hole->previous=tmp_hole->previous;
  969.         tmp_hole->previous=hole;
  970.         hole->next=tmp_hole;
  971.     }
  972.     hole=contour->next;
  973.     /* try once again - recurse */
  974.     return cut_out_hole(tobj,contour,hole);
  975. }
  976.  
  977. static GLenum merge_hole_with_contour(
  978.     GLUtriangulatorObj *tobj,
  979.     tess_contour *contour,
  980.     tess_contour *hole,
  981.     tess_vertex *v1,
  982.     tess_vertex *v2)
  983. {
  984.     tess_vertex *v1_new,*v2_new;
  985.  
  986.     /* make copies of v1 and v2, place them respectively after their originals */
  987.     if((v1_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  988.     {
  989.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  990.         return GLU_ERROR;
  991.     }
  992.     if((v2_new=(tess_vertex *)malloc(sizeof(tess_vertex)))==NULL)
  993.     {
  994.         tess_call_user_error(tobj,GLU_OUT_OF_MEMORY);
  995.         return GLU_ERROR;
  996.     }
  997.     v1_new->edge_flag=GL_TRUE;
  998.     v1_new->data=v1->data;
  999.     v1_new->location[0]=v1->location[0];
  1000.     v1_new->location[1]=v1->location[1];
  1001.     v1_new->location[2]=v1->location[2];
  1002.     v1_new->x=v1->x;
  1003.     v1_new->y=v1->y;
  1004.     v1_new->shadow_vertex=v1;
  1005.     v1->shadow_vertex=v1_new;
  1006.     v1_new->next=v1->next;
  1007.     v1_new->previous=v1;
  1008.     v1->next->previous=v1_new;
  1009.     v1->next=v1_new;
  1010.     v2_new->edge_flag=GL_TRUE;
  1011.     v2_new->data=v2->data;
  1012.     v2_new->location[0]=v2->location[0];
  1013.     v2_new->location[1]=v2->location[1];
  1014.     v2_new->location[2]=v2->location[2];
  1015.     v2_new->x=v2->x;
  1016.     v2_new->y=v2->y;
  1017.     v2_new->shadow_vertex=v2;
  1018.     v2->shadow_vertex=v2_new;
  1019.     v2_new->next=v2->next;
  1020.     v2_new->previous=v2;
  1021.     v2->next->previous=v2_new;
  1022.     v2->next=v2_new;
  1023.     /* link together the two lists */
  1024.     v1->next=v2_new;
  1025.     v2_new->previous=v1;
  1026.     v2->next=v1_new;
  1027.     v1_new->previous=v2;
  1028.     /* update the vertex count of the contour */
  1029.     contour->vertex_cnt += hole->vertex_cnt+2;
  1030.     /* remove the INTERIOR contour */
  1031.     contour->next=hole->next;
  1032.     if(hole->next!=NULL)
  1033.         hole->next->previous=contour;
  1034.     free(hole);
  1035.     /* update tobj structure */
  1036.     --(tobj->contour_cnt);
  1037.     if(contour->last_vertex==v1)
  1038.         contour->last_vertex=v1_new;
  1039.     /* mark two vertices with edge_flag */
  1040.     v2->edge_flag=GL_FALSE;
  1041.     v1->edge_flag=GL_FALSE;
  1042.     return GLU_NO_ERROR;
  1043. }
  1044.